//判断二叉树是不是二叉排序树
#include<stdio.h>
#include<stdlib.h>
#include <limits.h>


typedef struct Node
{
    int data;
    struct Node *lchild,*rchild;
}Node,*Tree;

int insertNode(Node *root,int data);
int preOrderPrintTree(Node *root);
void freeTree(Node *root);
int isBST(Node *root, int minValue, int maxValue);



int main(){
    int arr[5] = {3,2,4,5,6};
    Node root;
    root.data=-1;
    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
    {
        insertNode(&root,arr[i]);
    }
    preOrderPrintTree(&root);
    // freeTree(&root);
    int result = isBST(&root, INT_MIN, INT_MAX);
    if (result) {
        printf("这是一棵二叉排序树。\n");
    } else {
        printf("这不是一棵二叉排序树。\n");
    }
    //free不能释放指向的不是动态分配的内存（root）
    freeTree(root.lchild);
    freeTree(root.rchild);



    return 0;
}

Node* creatNode(int data){
    Node* node = (Node*)malloc(sizeof(Node));
    node->data=data;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}

int insertNode(Node *root,int data){
    if(root->data==-1){
        root->data=data;
        root->lchild=NULL;
        root->rchild=NULL;
        return 0;
    }
    if(root->data>=data){
        if(root->lchild==NULL){
            root->lchild=creatNode(data);
            return 0;
        }
        insertNode(root->lchild,data);
    }else{
        if(root->rchild==NULL){
            root->rchild=creatNode(data);
            return 0;
        }
        insertNode(root->rchild,data);
    }
    return 0;

}
int preOrderPrintTree(Node *root){
    if(root==NULL){
        return 0;
    }
    printf("%d ",root->data);
    preOrderPrintTree(root->lchild);
    preOrderPrintTree(root->rchild);
    return 0;
}

// 释放二叉树内存
void freeTree(Node *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->lchild);
    freeTree(root->rchild);
    free(root);
}

// 判断二叉树是否为二叉排序树
int isBST(Node *root, int minValue, int maxValue) {
    if (root == NULL) {
        return 1;
    }
    if (root->data <= minValue || root->data >= maxValue) {
        return 0;
    }
    return isBST(root->lchild, minValue, root->data) && isBST(root->rchild, root->data, maxValue);
}


